package com.sheng.leetcode.year2023.month08.day29;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author by ls
 * @date 2023/8/29
 * <p>
 * 823. 带因子的二叉树<p>
 * <p>
 * 给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。<p>
 * 用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。<p>
 * 满足条件的二叉树一共有多少个？答案可能很大，返回 对 10^9 + 7 取余 的结果。<p>
 * <p>
 * 示例 1:<p>
 * 输入: arr = [2, 4]<p>
 * 输出: 3<p>
 * 解释: 可以得到这些二叉树: [2], [4], [4, 2, 2]<p>
 * <p>
 * 示例 2:<p>
 * 输入: arr = [2, 4, 5, 10]<p>
 * 输出: 7<p>
 * 解释: 可以得到这些二叉树: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].<p>
 * <p>
 * 提示：<p>
 * 1 <= arr.length <= 1000<p>
 * 2 <= arr[i] <= 10^9<p>
 * arr 中的所有值 互不相同<p>
 */
public class LeetCode0823 {

    @Test
    public void test01() {
        int[] arr = {2, 4};
//        int[] arr = {2, 4, 5, 10};
//        int[] arr = {18, 3, 6, 2};
        System.out.println(new Solution().numFactoredBinaryTrees(arr));
    }
}

class Solution {

    public int numFactoredBinaryTrees(int[] arr) {
        // 思路：构建一个子树，要求使用 3 个元素(可重复)，并且满足两个子节点的乘积等于父节点
        long ans = 0;
        int n = arr.length;
        Arrays.sort(arr);
        // 创建数组并赋默认值，longs[i] 代表以 arr[i] 为根节点的二叉树的个数
        long[] longs = new long[n];
        Arrays.fill(longs, 1);
        // key 为数组的值，value 为数组元素对应的索引
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        for (int i = 0; i < n; i++) {
            // 根节点
            int x = arr[i];
            for (int j = 0; j < i; j++) {
                // 假设为左节点
                int y = arr[j];
                // 当 y 能被 x 整除时
                if (x % y == 0) {
                    // 获取右节点除数 z
                    int z = x / y;
                    // 当 z 也在数组中时，即可组成一个二叉树
                    if (map.containsKey(z)) {
                        // 获取元素 z 在数组中的索引
                        int m = map.get(z);
                        // 本身节点加上左右子树节点的组合方式
                        longs[i] = (longs[i] + longs[j] * longs[m]) % (int) (1e9 + 7);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            ans = (ans + longs[i]) % (int) (1e9 + 7);
        }
        return (int) ans;
    }
}
